package E_2024;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
    有一种特殊的加密算法，明文为一段数字串，经过密码本查找转换，生成另一段密文数字串。规则如下
    1.明文为一段数字串由0-9组成
    2.密码本为数字0-9组成的二维数组
    3.需要按明文串的数字顺序在密码本里找到同样的数字串，密码本里的数字串是由相邻的单元格数字组成，上下和左右是相邻的，注意:对角线不相邻，同一个单元格的数字不能重复使用。
    4.每一位明文对应密文即为密码本中找到的单元格所在的行和列序号(序号从0开始)组成的两个数字。如明文第位Data[i]对应密码本单元格为Book[x][y]，则明文第i位对应的密文为XY，X和Y之间用空格隔开
    如果有多条密文，返回字符序最小的密文。如果密码本无法匹配，返回"error"
    请你设计这个加密程序
示例1:
    密码本
    [0 0 2]
    [1 3 4]
    [6 6 4]
    明文:3,密文.“1 1”
示例2:
    密码本:
    0 0 2
    1 3 4
    6 6 4
    明文:“0 3”密文.“0 1 1 1”
 */
public class E_200_30 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(ans(new int[][]{{0, 0, 2}, {1, 3, 4}, {6, 6, 4}}, new int[]{0,3})));
        System.out.println(Arrays.toString(ans(new int[][]{{0, 0, 2}, {1, 3, 4}, {6, 6, 4}}, new int[]{3})));
    }
    public static int[] ans(int[][] arr, int[] temp){
        int[][] y = new int[arr.length][arr[0].length];
        int[] ans = new int[temp.length * 2];
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                if (arr[i][j] == temp[0]){
                    ans[0] = i;
                    ans[1] = j;
                    int[] dfs = dfs(arr, temp, i, j, 1, ans, y);
                    if (dfs != null) return dfs;
                }
            }
        }
        return ans;
    }
    public static int[] dfs(int[][] arr, int[] temp, int i, int j, int index, int[] ans, int[][] y){
        if (i < 0 || i == arr.length || j < 0 || j == arr[0].length || y[i][j] == 1) return null;
        if (index == temp.length) return ans;
        y[i][j] = 1;
        if (j < arr[0].length && y[i][j+1] == 0 && arr[i][j + 1] == temp[index]){
            ans[index * temp.length] = i;
            ans[index * temp.length + 1] = j+1;
            int[] dfs = dfs(arr, temp, i, j + 1, index + 1, ans, y);
            if (dfs != null) return dfs;
        }
        if (j > 0 && y[i][j-1] == 0 && arr[i][j - 1] == temp[index]){
            ans[index * temp.length] = i;
            ans[index * temp.length + 1] = j-1;
            int[] dfs = dfs(arr, temp, i, j - 1, index + 1, ans, y);
            if (dfs != null) return dfs;
        }
        if (i < arr.length && y[i+1][j] == 0 && arr[i + 1][j] == temp[index]){
            ans[index * temp.length] = i+1;
            ans[index * temp.length + 1] = j;
            int[] dfs = dfs(arr, temp, i + 1, j, index + 1, ans, y);
            if (dfs != null) return dfs;
        }
        if (i > 0 && y[i-1][j] == 0 && arr[i-1][j] == temp[index]){
            ans[index * temp.length] = i-1;
            ans[index * temp.length + 1] = j;
            return dfs(arr, temp, i-1, j, index + 1, ans, y);
        }
        return null;
    }
}
